﻿/*****************************************************
 * File:            GraphMST.cs
 * Description:     Finding the Minimal Spanning Tree of a graph (Prim Algorithm)
 * By:              Ali Khalili (khalili DOT ir AT gmail DOT com)
 * Project:         Automata Learning
 * Requirements:    Based on TranSys structure in EnGine
 * Change log:
 *          -4 May 2013:  Initial Development
 * To Do:
 *          -Write the Insert fucntion
 * License:
 *****************************************************/
using System;
using System.Collections.Generic;
using SMLib.Base;

namespace MBT.GraphAlgorithms
{
    /// <summary>
    /// Minimal Spanning Tree Finder: Prim's approach
    /// </summary>
    public class GraphMST<STATETYPE, TRANSITIONTYPE>
    {
        IDiGraph<STATETYPE, TRANSITIONTYPE> myGraph;
        TransitionCostAssigner<TRANSITIONTYPE> wHandler;

        /// <summary>
        /// Constructor
        /// </summary>
        /// <param name="graph">the graph to be used</param>
        /// <param name="weightFunction">the weight function</param>
        public GraphMST(IDiGraph<STATETYPE, TRANSITIONTYPE> graph, TransitionCostAssigner<TRANSITIONTYPE> weightFunction)
        {
            this.myGraph = graph;
            this.wHandler = weightFunction;
        }

        /// <summary>
        /// Constructor: FIND ANY SPANNING TREE
        /// </summary>
        /// <param name="graph">the graph to be used</param>
        public GraphMST(IDiGraph<STATETYPE, TRANSITIONTYPE> graph)
        {
            this.myGraph = graph;
            this.wHandler = DefaultWeight;
        }

        /// <summary>
        /// The default weight of transitoins are one
        /// </summary>
        /// <param name="t"></param>
        /// <returns></returns>
        int DefaultWeight(TRANSITIONTYPE t)
        {
            return 1;
        }

        /// <summary>
        /// Insert into list
        /// </summary>
        /// <param name="list"></param>
        /// <param name="elem"></param>
        void Insert(ref List<KeyValuePair<int, TRANSITIONTYPE>> list, KeyValuePair<int, TRANSITIONTYPE> elem)
        {
            int ind = 0;
            //* insert into empty list
            if (list.Count == 0)
            {
                list.Add(elem);
                return;
            }

            //* find the correct index
            ind = list.Count - 1;

            //* now, insert!
            list.Insert(ind, elem);

        }

        /// <summary>
        /// Find the MST of a graph
        /// </summary>
        /// <returns>list of transitions in the MST (which can be used to construct the MST)</returns>
        public List<TRANSITIONTYPE> FindMST()
        {
            List<TRANSITIONTYPE> edgesInMST = new List<TRANSITIONTYPE>();
            bool[] reached = new bool[myGraph.Size];

            //* preprocessing: the graph Structure
            List<List<TRANSITIONTYPE>> myEdges = new List<List<TRANSITIONTYPE>>();
            for (int i = 0; i < myGraph.Size; i++)
            {
                myEdges.Add(new List<TRANSITIONTYPE>());
                reached[i] = false;
            }

            //* Prim algorithm
            List<KeyValuePair<int, TRANSITIONTYPE>> sortedTrs = new List<KeyValuePair<int, TRANSITIONTYPE>>();
            reached[0] = true;
            foreach (TRANSITIONTYPE t in myGraph.TransitionsOf(myGraph[0]))
            {
                Insert(ref sortedTrs, (new KeyValuePair<int, TRANSITIONTYPE>(wHandler(t), t)));
            }

            int numberOfSelected = 1;
            while (sortedTrs.Count != 0 && numberOfSelected != myGraph.Size)
            {
                TRANSITIONTYPE minimalT = sortedTrs[0].Value;
                sortedTrs.RemoveAt(0);

                STATETYPE dest = myGraph.DestinationOf(minimalT);
                int destIndex = myGraph.IndexOf(dest);

                //* check the condition for loop 
                if (!reached[destIndex])
                {
                    reached[destIndex] = true;
                    myEdges[destIndex].Add(minimalT);
                    //* then, add all transitions
                    foreach (TRANSITIONTYPE t in myGraph.TransitionsOf(myGraph[destIndex]))
                    {
                    	if (!reached[myGraph.IndexOf(myGraph.DestinationOf(t))])
                            Insert(ref sortedTrs, (new KeyValuePair<int, TRANSITIONTYPE>(wHandler(t), t)));
                    }
                }
            }

            //* post processing: list all
            for (int i = 0; i < myGraph.Size; i++)
            {
                edgesInMST.AddRange(myEdges[i]);
            }
            return edgesInMST;
        }
    }
}
